In a conventional computer system, processes are managed by an operating system such as DOS or OS/2, which in turn supports an application program such as a word processor or spreadsheet. The application program is largely responsible for determining what input or output is necessary, but only communicates with the input/output devices via the operating system. Thus, the application program might send a request for a particular output; message to the operating system, which is the responsible for writing the message onto the output display screen.
The actual display on the screen at any one time is determined by the contents of a hardware frame buffer. This buffer usually contains the actual pixel intensities and colors, although there can be another hardware logic processing stage between the frame buffer and the screen itself (for example, the frame buffer may contain text strings which the logic then processes into pixel patterns). Thus, in order to change the display, the operating system updates the frame buffer, and the output on the screen is then altered accordingly. The frame buffer and logic are implemented in hardware because the data rate to the screen is very high; typically on the order of Megabytes per second. This is also the reason that image processing imposes such large computing overheads.
Many modern operating systems provide a graphical user interface (GUI) in which the user can control the position of a cursor on the screen by moving a mouse device. The operating system monitors the physical movement of the mouse and translates this into the corresponding screen position of the cursor. To select a particular point on the screen, the user presses a button on the mouse when the cursor coincides with that point. Again, this user selection of a particular position is first received by the operating system before forwarding to the application program. Typically, the selected position might represent the user's choice of one of several icons or other shapes currently displayed on the screen. These shapes can represent, for example, files to be processed or components of a drawing to be manipulated.
The present invention is concerned with the correlation of a cursor-selected position with the displayed shapes, to determine which shape (or shapes) the user has actually chosen. This correlation is sometimes provided by the operating system, but if not, the application program must do the correlation itself. In either case, the process must be completed in a fraction of a second unless the user is to notice an intrusive delay.
While it is relatively easy for the user to discern which shape is being selected, this is a much more difficult task for the software controlling the computer (whether operating system or application program). It is straightforward enough to obtain the contents of any one screen pixel by interrogating the frame buffer, but this only reveals the current value of the pixel. This will, therefore, not allow a distinction to be made between, for example, two shapes that have the same intensity and color. Furthermore, because of the high data rate involved, it is not possible to separately store screen data, with added information to identify the shapes. Although, in theory, the correlation could be performed by re-calculating the pixels occupied by every shape, (this is, indeed, how the operating system draws the shape in the first place) this is far too expensive in terms of computer processing time and cannot be done quickly enough. Time constraints become even more acute if the user selected position has to be checked against many different shapes displayed simultaneously on the screen.
One way of reducing the amount of computation required is to calculate a bounding rectangle for each shape. The bounding rectangle is defined as the smallest rectangle (with horizontal and vertical edges) that completely encloses a particular shape. The selected position is then correlated, not against the shape itself, but against the bounding rectangle instead. This approach is much simpler computationally and faster, but can produce an incorrect correlation if the selected position is outside a particular shape, but within its associated bounding rectangle.